package com.yoshino.leetcode.improve40.Threetyseventh;

import java.util.*;

class Solution {

    List<List<Integer>> res;
    boolean[] visited;
    int n;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        res = new ArrayList<>();
        n = graph.length;
        visited = new boolean[n];
        dfs(0, graph, new ArrayList<Integer>());
        return res;
    }

    private void dfs(int cur, int[][] graph, ArrayList<Integer> tmp) {
        if (cur == n - 1) {
            tmp.add(n - 1);
            res.add(new ArrayList<>(tmp));
            return;
        }
        tmp.add(cur);
        for (int next : graph[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                dfs(next, graph, tmp);
                visited[next] = false;
                // 传递的是地址
                tmp.remove(tmp.size() - 1);
            }
        }

    }

    public int openLock(String[] deadends, String target) {
        // 每次转动一个位置；用哈希记录死锁情况；队列来存储当前可能的所有情况
        if ("0000".equals(target)) {
            return 0;
        }

        Set<String> dead = new HashSet<>();
        for (String deadend : deadends) {
            dead.add(deadend);
        }

        if (dead.contains("0000")) {
            return -1;
        }

        int step = 0;
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        // 已找过
        Set<String> found = new HashSet<>();
        found.add("0000");
        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                // 判断转动一次后是否符合条件，否则进行下次循环
                for (String next : get(cur)) {
                    if (!found.contains(next) && !dead.contains(next)) {
                        // 没找过，且不死锁
                        if (next.equals(target)) {
                            return step;
                        }
                        queue.offer(next);
                        found.add(next);
                    }
                }
            }
        }
        return -1;
    }

    private List<String> get(String cur) {
        List<String> res = new ArrayList<>();
        char[] copy = cur.toCharArray();
        for (int i = 0; i < 4; i++) {
            char c = copy[i];
            // 判断转过头
            copy[i] = numPrev(c);
            res.add(new String(copy));
            copy[i] = numNext(c);
            res.add(new String(copy));
            copy[i] = c;
        }
        return res;
    }

    private char numPrev(char cur) {
        return cur == '0' ? '9' : (char) (cur - 1);
    }

    private char numNext(char cur) {
        return cur == '9' ? '0' : (char) (cur + 1);
    }
}